﻿#pragma once

#include <iostream>
#include <unordered_map>
#include <map>
#include <cassert>
#include <ctime>
#include <thread>
#include <mutex>
#include <atomic>
#include <algorithm>

static const int MAX_SIZE = 256 * 1024;
static const int NFREE_LISTS = 208; // 自由链表的数量
static const int PAGE_SHIFT = 13; // 页的二进制位数
static const int NPAGES = 129; // page cache中的哈希桶个数
static const int PAGE = 8 * 1024; // 一个页的字节数

// 注意：在32位平台下，定义了_WIN32的宏。在64位平台下，定义了_WIN32、_WIN64的宏

#ifdef _WIN32
#include <windows.h>
#else
#include <unistd.h>
#endif 

#ifdef _WIN32
typedef size_t PAGE_ID;
#else 
using PAGE_ID = size_t;
#endif 

static inline void* SystemAlloc(PAGE_ID kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	void* ptr = sbrk(kpage << PAGE_SHIFT);
	if (ptr == static_cast<void*>(-1))
	{
		throw bad_alloc();
	}
#endif
	return ptr;
}

static inline void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else // Linux...
	// sbrk、ummap等
	if (brk(ptr) == -1)
	{
		throw bad_alloc();
	}
#endif
}

static void*& NextObj(void* obj)
{
	if (obj == nullptr)
	{
		std::cout << obj << std::endl;
		
	}

	assert(obj);
	return *(void**)obj;
}

// 自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);

		// 头插
		// *(void**)obj = _head;
		NextObj(obj) = _head;
		_head = obj;
		++_size;
	}

	void* Pop()
	{
		assert(_head);

		// 头删
		void* obj = _head;
		_head = NextObj(_head);
		--_size;

		return obj;
	}

	bool Empty()const
	{
		return _head == nullptr;
	}

	size_t Size()
	{
		return _size;
	}

	size_t& MaxSize() { return _maxSize;}

	// 插入一批内存块
	void PushRange(void* start, void* end, size_t n)
	{
		// 头插
		NextObj(end) = _head;
		//观察插入的是否是n个
		void* tmp = start;
		size_t k = 0;
		while (tmp)
		{
			tmp = NextObj(tmp);
			++k;
		}

		if (k != n)
		{
			std::cout << "PushRange: k != n" << std::endl;
		}

		_head = start;
		_size += n;
	}

	// 删除一批内存块
	void PopRange(void*& start, void*& end, size_t size)
	{
		assert(size <= _size);

		void* tmp = _head;
		size_t k = 0;
		while (tmp)
		{
			tmp = NextObj(tmp);
			k++;
		}

		if (size > k + 1)
		{
			std::cout << "PopRange error!" << std::endl;
		}

		start = _head;
		end = _head;
		for (size_t i = 1; i < size; i++)
		{
			end = NextObj(end);
		}

		_head = NextObj(end);
		NextObj(end) = nullptr;
		_size -= size;
	}

//private:
	void* _head = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

struct Span
{
	PAGE_ID _pageId = 0;		// 大块内存的页号
	size_t _pageNum = 0;		// 页的数量
	Span* _next = nullptr;		// 双向链表
	Span* _prev = nullptr;
	size_t _useCount = 0;		// 小块内存被使用数量
	void* _freeList = nullptr;	// 大块内存划分成小块内存
	size_t _objSize = 0;		// 切分对象的大小
	bool _isUse = false;
};

class SpanList
{
public:
	SpanList()
		:_head(new Span)
	{
		_head->_next = _head;
		_head->_prev = _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;

		// 插入链接
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void PushFront(Span* span) { Insert(Begin(), span);}

	Span* PopFront()
	{
		assert(_head->_next != _head);
		// 代码复用
		Span* obj = _head->_next;
		Erase(Begin());
		return obj;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	std::mutex& GetMutex() { return _mtx;}

	Span* Begin() { return _head->_next;}

	Span* End() { return _head;}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
		// 注意：这里不需要delete
	}

private:
	Span* _head;
	std::mutex _mtx; // 每一个SpanList都需要配套一个mutex
};

class SizeClass
{
	// 整体控制在最多10%左右的内碎片浪费
	// 8字节：
	// 7 / 8		约等于90%
	// 7 / 16		约等于50%
	// 7 / 24		约等于37%
	// 7 / 128		约等于10%
	// 16字节：
	// 15 / 129		约等于10%
	// 15 / 1024	约等于1%
	// ......
	
	// 后面的浪费会越来越少
	// [1,128]					8byte对齐			freelist[0,16)
	// [128+1,1024]				16byte对齐			freelist[16,72)
	// [1024+1,8*1024]			128byte对齐			freelist[72,128)
	// [8*1024+1,64*1024] 		1024byte对齐			freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐		freelist[184,208)
public:
	// 找到当前应该申请内存的大小
	static inline size_t _RoundUp(size_t bytes, size_t align)
	{
		// assert(bytes <= MAX_SIZE);

		// eg：申请5字节为例
		// align == 8							==》 0000 0000 0000 0000 0000 0000 0000 1000
		// align - 1 == 7						==》 0000 0000 0000 0000 0000 0000 0000 0001
		// ~ (align - 1)						==》 1111 1111 1111 1111 1111 1111 1111 1000
		// bytes + align - 1 = 11				==》 0000 0000 0000 0000 0000 0000 0000 1011
		// (bytes + align - 1) & ~ (align - 1)	==》 0000 0000 0000 0000 0000 0000 0000 1000
		// 使用位运算，效率更高
		return ((bytes + align - 1) & ~ (align - 1));

		// return bytes % align == 0 ? bytes : (bytes / align + 1) * align;
	}

	static inline size_t RoundUp(size_t size)
	{
		 assert(size <= MAX_SIZE); // 256K

		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			//assert(false);
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	// 找到对应内存大小的哈希桶的下标（CentralCache的_SpanList）
	//static size_t _GetBucketIndex(size_t bytes, size_t align)
	//{
	//	return bytes % align == 0 ? bytes / align - 1 : bytes / align;
	//}
	static inline size_t _GetBucketIndex(size_t bytes, size_t alignShift)
	{
		return ((bytes + (1 << alignShift) - 1) >> alignShift) - 1;
	}

	static inline size_t GetBucketIndex(size_t bytes)
	{
		assert(bytes <= MAX_SIZE);
		assert(bytes != 0);

		static int sizeArray[4] = { 16, 56, 56, 56 };
		size_t index = 0;
		if (bytes <= 128)
		{
			// 使用位运算
			index = _GetBucketIndex(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			index = _GetBucketIndex(bytes - 128, 4) + sizeArray[0];
		}
		else if (bytes <= 8 * 1024)
		{
			index = _GetBucketIndex(bytes - 1024, 7) + sizeArray[0] + sizeArray[1];
		}
		else if (bytes <= 64 * 1024)
		{
			index = _GetBucketIndex(bytes - 8 * 1024, 10) + sizeArray[0] + sizeArray[1] + sizeArray[2];
		}
		else if (bytes <= 256 * 1024)
		{
			index = _GetBucketIndex(bytes - 64 * 1024, 13) + sizeArray[0] + sizeArray[1] + sizeArray[2] + sizeArray[3];
		}
		else
		{
			assert(false);
		}
		return index;
	}

	// Thread Cache一次从Central Cache获取多少个当前小内存块
	static size_t NumMoveSize(size_t size)
	{
		assert(size);

		// 慢启动算法
		size_t num = MAX_SIZE / size;

		if (num < 2)
		{
			num = 2;
		}
		else if (num > 512)
		{
			num = 512;
		}

		return num;
	}

	// 计算CentralCache需要向PageCache获取内存的页数
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t nPage = (num * size) >> PAGE_SHIFT;

		if (nPage < 1)
		{
			nPage = 1;
		}

		return nPage;
	}
};